package FourArithmeticOperations;

import com.sun.org.apache.bcel.internal.generic.ARRAYLENGTH;

import java.util.ArrayList;

/**
 * Created by dell on 2017/11/1.
 */
public class HuffmanTree                                   //Huffman树类
{
    private String charset;                                //字符集合
    private TriElement[] huftree;                          //静态三叉链表结点数组

    //构造Huffman树，weights指定权值集合，数组长度为叶子结点数；默认字符集合从A开始
    public HuffmanTree(int[] weights) {
        this.charset = "";
        for (int i = 0; i < weights.length; i++)               //默认字符集合是从'A'开始的weights.length个字符
            this.charset += (char) ('A' + i);

        int n = weights.length;                            //叶子结点数
        this.huftree = new TriElement[2 * n - 1];              //n个叶子的Huffman树共有2n-1个结点
        for (int i = 0; i < n; i++)                             //Huffman树初始化n个叶子结点
            this.huftree[i] = new TriElement(weights[i]);  //构造无父母的叶子结点

        for (int i = n; i < 2 * n - 1; i++)                         //构造n-1个2度结点
        {
            int min1 = Integer.MAX_VALUE, min2 = min1;         //最小和次小权值，初值为整数最大值
            int x1 = -1, x2 = -1;                              //最小和次小权值结点下标
            for (int j = 0; j < i; j++)                        //寻找两个无父母的最小权值结点下标
                if (this.huftree[j].parent == -1)            //第j个结点无父母
                    if (this.huftree[j].data < min1)         //第j个结点权值最小
                    {
                        min2 = min1;                       //min2记得次小权值
                        x2 = x1;                           //x2记得次小权值结点下标
                        min1 = this.huftree[j].data;       //min1记得最小权值
                        x1 = j;                            //x1记得最小权值结点下标
                    } else if (this.huftree[j].data < min2)     //第j个结点权值次小
                    {
                        min2 = huftree[j].data;
                        x2 = j;
                    }

            this.huftree[x1].parent = i;                   //合并两棵权值最小的子树，左孩子最小
            this.huftree[x2].parent = i;
            this.huftree[i] = new TriElement(min1 + min2, -1, x1, x2); //构造结点，指定值、父母、左右孩子
        }
    }

    private String getCode(int i)                 //返回charset第i个字符的Huffman编码字符串
    {
        int n = 8;
        char hufcode[] = new char[n];                      //声明字符数组暂存Huffman编码
        int child = i, parent = this.huftree[child].parent;
        for (i = n - 1; parent != -1; i--)                       //由叶结点向上直到根结点，反序存储编码
        {
            hufcode[i] = (huftree[parent].left == child) ? '0' : '1';  //左、右孩子编码为0、1
            child = parent;
            parent = huftree[child].parent;
        }
        return new String(hufcode, i + 1, n - 1 - i);    //由hufcode数组从i+1开始的n-1-i个字符构造串
    }

    public String toString()                     //返回Huffman树的结点数组和所有字符的编码字符串
    {
        String str = "Huffman树的结点数组:";
        for (int i = 0; i < this.huftree.length; i++)
            str += this.huftree[i].toString() + "，";
        str += "\nHuffman编码： ";
        for (int i = 0; i < this.charset.length(); i++)        //输出所有叶子结点的Huffman编码
            str += this.charset.charAt(i) + "：" + getCode(i) + "，";
        return str;
    }

    //数据压缩，将text各字符转换成Huffman编码存储，返回压缩字符串
    public String encode(String text) {
        String compressed = "";                              //被压缩的数据，以字符串显示
        for (int i = 0; i < text.length(); i++)
            compressed += getCode(text.charAt(i) - 'A');     //默认字符集是从A开始的n个字符
        return compressed;
    }

    //数据解压缩，将压缩compressed中的0/1序列进行Huffman译码，返回译码字符串
    public String decode(String compressed) {
        ArrayList list = new ArrayList();
        ArrayList<String> list1 = new ArrayList();
        LinkedQueue queue = new LinkedQueue();
        for (int i = 0; i < this.charset.length(); i++) {   //输出所有叶子结点的Huffman编码
            list.add(this.charset.charAt(i));
            list1.add(getCode(i));
        }
        int i = 0;
        String s1 = " ";
        while (i < compressed.length()) {
            String s = String.valueOf(compressed.charAt(i));
            if (s.equals(list1.get(0))) {
                s1 += list.get(0);
                i++;
            } else {
                String s2 = String.valueOf(compressed.charAt(i + 1));
                String s3 = s + s2;
                if (s3.equals(list1.get(1))) {
                    s1 += list.get(1);
                    i = i + 2;
                } else {
                    String s4 = String.valueOf(compressed.charAt(i + 2));
                    String s5 = s3 + s4;
                    if (s5.equals(list1.get(2))) {
                        s1 += list.get(2);
                        i = i + 3;
                    } else {
                        s1 += list.get(3);
                        i = i + 3;
                    }
                }
            }
        }
        return s1;
    }
}